1. Field of the Invention
This invention relates to the field of multiple processor systems. More particularly, this invention relates to a method and apparatus for transporting messages between processors in a multiple processor system.
2. Description of the Related Art
A message is simply a data structure for conveying operational parameters and data. Messages are generated by one or more processes (i.e., applications) executing on one or more platforms. A platform includes a processor or cluster of processors, associated memory, and a local memory bus, and a memory input/output bus. These elements within a platform make up an operating environment.
Moreover, a platform executes a single instance of an operating system. In other words the computer system is a distributed processing system in which a single operating system supports multiple processors. After a message is generated by one of the processes on one particular platform, it is sent to another processor platform for processing.
A message may be indicated by a pointer to a control block, residing in memory, that includes instructions and other pointers to additional data blocks of information. For example, a control block may specify a particular peripheral device (i.e., a hard disk drive), and request that data be read from specified sectors of the device.
Message passing is used between processors in a symmetric multiple processor system (SMP) where the processors are "tightly coupled" (i.e., where processors share a single cache) and in asymmetric multiple processor systems, where processors are "loosely" coupled together by a common bus structure.
When a message is passed from one processor in a first platform to a second processor in a second platform, there is a need for the message to be queued so that the processor, to which the message is directed, may process the message when its resources are free.
The prior art methods for queuing messages are primarily implemented using software techniques. These methods require multiple atomic accesses to shared queue structures. For example, a plurality of processes, running on a single processor, may share one queue of messages, located in a memory shared by the processors. To achieve an atomic access for one of the processes, an operating system grants to the process, requesting access to the queue, a semaphore that gives that process exclusive rights (i.e., atomic access) to the queue. A semaphore is simply an operating system variable that gives a process exclusive access to a shared data structure (i.e., part of the operating system context). The process may then add or remove a message from the queue. When a particular process controls the semaphore, it locks out other processes requiring access to that queue. The other processes must wait for the first process to release the semaphore before access to the shared structure is available.
In a multiple processor system, more than one processor could be trying to gain access to the semaphore concurrently. Thus, a bus lock is required for synchronization (i.e., atomic access). While one processor has the bus locked, another processor cannot access the same shared structure in memory (i.e., a memory block) until the first processor unlocks the bus. Since semaphores are in system memory, the other processors are locked out even though they are not contending for a semaphore. Therefore, a bus lock can never be used in a software module that can be suspended (i.e., a multi-tasking operating system). Instead, a call to the operating system kernel is required when obtaining and releasing a semaphore in these applications.
The above-described operation is very inefficient because of the amount of time each process spends idle while waiting for semaphores or waiting for bus access. Furthermore, the above-described calls to an operating system kernel cause expensive context switches.
Context is simply a memory area that is dedicated to an application (i.e., application code and data). An application context includes flags, variables, and states of a current process. Since a semaphore is an operating system variable in a different context (i.e., an operating system context) than an application context, system resources are necessary to switch contexts. For example, in a context switch data pointers are changed, pointers are pushed onto stacks, and process control parameters are also modified.
Prior art computer systems that do not have a bus lock capability use highly complex algorithms to provide synchronization between processors. In these systems, performance is further reduced.
Thus, there is a need for a method and apparatus for efficiently allowing direct access to the queues without the use of semaphores.